package digit

import (
	"gitee.com/jinyunliu/algorithm/util"
	"math"
	"sort"
	"strconv"
	"strings"
)

// ReverseInteger [-2^31, 2^31-1]
// leetcode7  反转整数
func ReverseInteger(x int) int {
	y := 0
	for x != 0 {
		y = y*10 + x%10
		if y < math.MinInt32 || y > math.MaxInt32 {
			return 0
		}

		x = x / 10
	}

	return y
}

// Atoi 字符串转int
// leetcode8
// "-2147483648"
func Atoi(s string) int {
	// 去除空串
	s = strings.Trim(s, " ")
	if len(s) == 0 {
		return 0
	}

	var (
		res  = 0
		sign = 1
		i    = 0
	)

	if s[0] == '-' {
		sign = -1
		i++
	} else if s[0] == '+' {
		i++
	}

	// 通过 后面 s0[0] == - 进行取反
	for ; i < len(s); i++ {
		if s[i] < '0' || s[i] > '9' {
			return res * sign
			// 这个是界的判断;
		} else if res > math.MaxInt32/10 || res == math.MaxInt32/10 && int(s[i]-'0') > math.MaxInt32%10 {
			if sign == 1 {
				return math.MaxInt32
			} else {
				return math.MinInt32
			}
		} else {
			res = res*10 + int(s[i]-'0')
		}
	}

	return res * sign
}

// IsPalindrome 是否是回文数
// leetcode9
// Level: easy  不能将这个x 转成字符串处理;
func IsPalindrome(x int) bool {
	if x < 0 {
		return false
	}

	if x < 10 {
		return true
	}

	var (
		s     = strconv.Itoa(x)
		left  = 0
		right = len(s) - 1
	)

	for left <= right {
		if s[left] != s[right] {
			return false
		}

		left++
		right--
	}

	return true
}

// IsPalindrome2 不将int 转成string
// leetcode9  回文数
func IsPalindrome2(x int) bool {
	if x < 0 {
		return false
	}

	var (
		y   = x
		res = 0
	)

	for x != 0 {
		res = res*10 + x%10
		x = x / 10
	}

	return y == res
}

// IntToRoman 整形转罗马
// leetcode12 整形转罗马
func IntToRoman(num int) string {
	var (
		val   = []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
		roman = []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
		res   = ""
	)

	for i := 0; i < len(val); i++ {
		for num >= val[i] {
			num -= val[i]
			res += roman[i]
		}
	}

	return res
}

// RomanToInt 罗马转整型
// leetcode13 罗马转整型
func RomanToInt(s string) int {
	var (
		roman = []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
		hash  = map[string]int{
			"M":  1000,
			"CM": 900,
			"D":  500,
			"CD": 400,
			"C":  100,
			"XC": 90,
			"L":  50,
			"XL": 40,
			"X":  10,
			"IX": 9,
			"V":  5,
			"IV": 4,
			"I":  1,
		}
		res = 0
	)

	for i := 0; i < len(roman); i++ {
		for strings.HasPrefix(s, roman[i]) {
			res += hash[roman[i]]
			s = s[len(roman[i]):]
		}
	}

	return res
}

// ThreeSum 给你一个包含 n 个整数的数组nums
// 判断nums中是否存在三个元素使得a + b + c = 0 且不重复的三元组 set 不考虑order
// leetcode15 三数之和
func ThreeSum(nums []int) [][]int {
	res := make([][]int, 0)
	if len(nums) < 3 {
		return res
	}
	// how to evict the duplicates?  tuple: a + b + c = 0  answer: 排序
	sort.Ints(nums)
	for i := 0; i < len(nums)-2; i++ {
		// 1. 已经从小到大排序了 如果第一个大于0 就不能出现 和=0
		if nums[i] > 0 {
			return res
		}

		// 2. 已经排好序 如果当前的值和前面的值一样 无需重复计算
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}

		// 等价于; 在 [i+1, len-1] 中查询连个值 == -nums[i] >=0 注意这是一个有序序列 重复的应该不在处理
		left, right := i+1, len(nums)-1
		for left < right {
			mr := nums[left] + nums[right] + nums[i]
			if mr > 0 {
				// 如果右边的很大 都是相同的; 直接把相同的全部抹掉
				for right = right - 1; right > 0; right-- {
					if nums[right] != nums[right+1] {
						break
					}
				}
			} else if mr < 0 {
				for left = left + 1; left < len(nums)-1; left++ {
					if nums[left] != nums[left-1] {
						break
					}
				}
			} else {
				res = append(res, []int{nums[i], nums[left], nums[right]})

				for right = right - 1; right > 0; right-- {
					if nums[right] != nums[right+1] {
						break
					}
				}

				for left = left + 1; left < len(nums)-1; left++ {
					if nums[left] != nums[left-1] {
						break
					}
				}
			}
		}
	}

	return res
}

// ThreeSumClosest 最接近3数之和
// leetcode16:  最接近3数之和  题目至少给3个数  每次输入仅有唯一答案
func ThreeSumClosest(nums []int, target int) int {
	var (
		d   = math.MaxInt32
		res int
	)
	sort.Ints(nums)
	for i := 0; i < len(nums)-2; i++ {
		for l, r := i+1, len(nums)-1; l < r; {
			s := nums[i] + nums[l] + nums[r]
			if s > target {
				if util.Abs(s-target) < d {
					d = util.Abs(s - target)
					res = s
				}
				r--
			} else if s < target {
				if util.Abs(target-s) < d {
					d = util.Abs(s - target)
					res = s
				}
				l++
			} else {
				return target
			}
		}
	}

	return res
}

// FourSum 四数之和 和 前面那个3数之和类似 都要求返回等于目标值的不重复元组
// leetcode18 四数之和
func FourSum(nums []int, target int) [][]int {
	res := make([][]int, 0)
	if len(nums) < 4 {
		return res
	}

	sort.Ints(nums)
	// nums[i] 在 [i+1, len)   find    3个数的和 == target - nums[i]
	for i := 0; i < len(nums)-3; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}

		for j := i + 1; j < len(nums)-2; j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}

			l, r := j+1, len(nums)-1
			for l < r {
				s := nums[i] + nums[j] + nums[l] + nums[r]
				if s < target {
					l++
				} else if s > target {
					r--
				} else {
					res = append(res, []int{nums[i], nums[j], nums[l], nums[r]})
					for l = l + 1; l < r && nums[l] == nums[l-1]; l++ {
					}
					for r = r - 1; l < r && nums[r] == nums[r+1]; r-- {
					}
				}
			}
		}
	}

	return res
}

// 两数之和
// 三数之和
// 最接近三数之和
// 4数之和
// 遇到这类 直接先 排序并且进行去重 然后在处理 逻辑就简单多了  不会在处理中考虑去重的问题; 还不能直接去重, 因为存在重复的问题;

// Divide 除法 要求 不能使用 / %  返回整数
// leetcode29 整数除法
func Divide(dividend int, divisor int) int {
	return 0
}

// 有一个倍增的模板
